class Solution
{
public:
    vector<int> goodIndices(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> maxLeftNonIncLen(n);
        vector<int> maxRightNonDecLen(n);
        int firstLeftNonInc = 1;
        for (int i = k - 2; i >= 0; --i)
        {
            if (nums[i] >= nums[i + 1])
            {
                ++firstLeftNonInc;
            }
            else
            {
                break;
            }
        }
        maxLeftNonIncLen[k] = firstLeftNonInc;
        for (int i = k + 1; i < n - k; ++i)
        {
            if (nums[i - 1] <= nums[i - 2])
            {
                maxLeftNonIncLen[i] = maxLeftNonIncLen[i - 1] + 1;
            }
            else
            {
                maxLeftNonIncLen[i] = 1;
            }
        }
        int lastRightNonInc = 1;
        for (int i = n - k + 1; i < n; ++i)
        {
            if (nums[i] >= nums[i - 1])
            {
                ++lastRightNonInc;
            }
            else
            {
                break;
            }
        }
        maxRightNonDecLen[n - k - 1] = lastRightNonInc;
        for (int i = n - k - 2; i >= k; --i)
        {
            if (nums[i + 1] <= nums[i + 2])
            {
                maxRightNonDecLen[i] = maxRightNonDecLen[i + 1] + 1;
            }
            else
            {
                maxRightNonDecLen[i] = 1;
            }
        }
        vector<int> goodIdx;
        for (int i = k; i < n - k; ++i)
        {
            if (min(maxLeftNonIncLen[i], maxRightNonDecLen[i]) >= k)
            {
                goodIdx.push_back(i);
            }
        }
        return goodIdx;
    }
};